1. Field of the Invention
This invention relates generally to storage buffers for storing serial data, and more particularly to FIFO buffers.
2. Discussion of the Related Art
FIG. 1A depicts a typical data stream in which data is conveyed as data groups of varying length. In the illustrated example a single data group may be one, two, or four 8-byte data units long.
FIG. 1B depicts a conventional FIFO (first in, first out) buffer 100 that includes four 32-byte storage elements 102, 104, 106, and 108. Each storage element includes a valid bit V which stores a logic one to indicate that the respective storage element contains valid data or a logic zero to indicate that the storage element may be overwritten.
Data is written into FIFO buffer 100 via an input bus 110 and read out via an output bus 112. A conventional FIFO control block (not shown) generates write and read pointers for FIFO buffer 100. The write pointer indicates the memory element currently being written to; the read pointer indicates the memory element being read from. The valid bits V are logically combined using conventional logic to avoid overflowing FIFO buffer 100 with data.
FIFO buffer 100 is shown to contain the contents of the data stream of FIG. 1A. The first data group D000, four units long, is stored in storage element 108. Because data group D000 was written to FIFO buffer first (i.e., was "first in"), data group D000 is also read from FIFO buffer first (i.e., is "first out"). The following three data groups D001, D010, and D011 are subsequently stored in respective storage elements 106, 104, and 102.
The shaded storage locations of FIFO buffer 100 illustrate that storing data in data groups of varying length leads to inefficient packing of FIFO buffer 100. The valid bits V of FIFO buffer 100 indicate that FIFO buffer 100 is full despite the presence of five empty storage locations. Consequently, subsequent data coming from input bus 110 must be stalled until data group D000 is read from FIFO buffer 100.